class Node:
    def __init__(self, weight):
        # 节点的权值
        self.weight = weight
        self.left = None
        self.right = None
        # 是否新构造的根节点，新构造的根节点在WPL中不参与计算
        self.isNew = False

    def __gt__(self, other):

        """
        用于对节点之间的排序
        """
        return self.weight > other.weight

class huffmanTree(object):
    def __init__(self, data):
        self.WPL = 0
        self.root = self.createHuffmanTree(data)

    def createHuffmanTree(self, data):
        """
        创建哈夫曼树
        :parm data: 森林中的单个节点构成的二叉树
        """
        while len(data) != 1:
            data.sort()
            left = data.__getitem__(0)
            right = data.__getitem__(1)
            newNode = Node(left.weight + right.weight)
            newNode.isNew = True
            newNode.left = left
            newNode.right = right
            data.pop(0)
            data.pop(0)
            data.appent(newNode)